package cn.walls1717.leetcode.array;

/**
 * 209. 长度最小的子数组
 * 力扣地址：https://leetcode-cn.com/problems/minimum-size-subarray-sum/
 *
 * @author walls1717
 * @since 2022-5-5
 */
public class T209 {

    public static void main(String[] args) {
        int[] nums = {2, 3, 1, 2, 4, 3};
        int target = 7;
        System.out.println(minSubArrayLen(target, nums));
    }

    /**
     * 暴力解决
     *
     * @param target target
     * @param nums   数组
     * @return 长度
     */
    public static int minSubArrayLen(int target, int[] nums) {
        // 先判断数组长度，如果数组长度为空，直接返回 0
        if (nums.length == 0) {
            return 0;
        }
        // 先定义结果变量，将整数最大值赋值给它
        int ans = Integer.MAX_VALUE;
        // 用来存储数组中元素相加之和
        int sum;
        /*
        第一个 for 循环先确定 i 的位置，然后循环 j 的位置
        把 i 与 j 对应的元素进行相加，如果满足条件，则在 ans 中
        选择一个最小值，结束循环，直到大循环结束，找到最小的 ans
         */
        for (int i = 0; i < nums.length; ++i) {
            sum = 0;
            for (int j = i; j < nums.length; ++j) {
                sum += nums[j];
                if (sum >= target) {
                    ans = Math.min(ans, j - i + 1);
                    break;
                }
            }
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }

    /**
     * 滑动数组解决
     * 设置两个指针，同时指向数组头部
     * 进入循环，右指针先遍历，同时 sum 存储右指针遍历元素之和
     * 如果这个数大于等于目标值了，就给结果变量赋值，
     * 然后移动左指针，同时删除元素和中右指针指向的元素，
     * 直到元素和小于目标值，再次遍历左指针，直到遍历完整个数组
     *
     * @param target 目标值
     * @param nums   数组
     * @return 长度
     */
    public int minSubArrayLen2(int target, int[] nums) {
        // 左指针
        int left = 0;
        // 元素和
        int sum = 0;
        // 结果变量
        int ans = Integer.MAX_VALUE;
        // 右指针也就是慢指针，左指针是快指针
        for (int right = 0; right < nums.length; ++right) {
            // 快指针前移，元素相加
            sum += nums[right];
            /*
             判断元素和是否大于等于目标值
             如果满足条件，要一直前移慢指针
             直到不满足条件，进行下一轮循环
             */
            while (sum >= target) {
                // 将最小值给 ans
                ans = Math.min(ans, right - left + 1);
                // 慢指针前移，要相同的减掉其在元素和中对应的元素
                sum -= nums[++left];
            }
        }
        // 如果 ans 的值改变了，则取到最小值，如果没有，则说明数组不满足条件，直接返回 0
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}
